配送路线优化:车辆线路安排问题vehicle routing problem

是指物流配送的车辆进行优化调度，对一系列装货点和卸货点组织适当合理的行车路线，使车辆有序地通过它们，在满足一定的条件下（如货物需求量、发送量、交发货时间、车辆容量、数目限制车辆行驶里程、时间限制等），达到一定的目标（如最短路程、最小费用、最短时间、最小车辆）;

确定配送路线的约束条件

a 客户要求：客户常对配送运输提出自己的要求：“在正确的时间，将正确的物品以正确的数量送到正确的地点”；

b 道路限制：车辆运送所经道路状况，如限行、限高、限速等都是影响路线设计必须考虑的因素；路程的远近是否超过了驾驶员所能承受的范围；

c 车辆限制：车辆载重量的大小、数量的多少、功能的区别等因素都是配送时安排车辆的限制条件；

d 人员限制：出于安全的考虑，驾驶员必须有合理的间隔休息时间。

配送问题的最优解实际就是一个有效的车辆调度问题，它应该明确地规定在满足约束条件下派车的数量、类型和各个车辆的路线，在完成运输任务的前提下，便得目标最大化；

1 节约里程法的基本设定

1.1 配送的是同一种货物；      

1.2 各客户的坐标及需求量均为已知；

1.3 配送中心有足够的运输能力；

2 绘制配送中心与配送点以及配送点之间的坐标及最短距离的标注；

3 配送中心有两种货车：1.5T，4T；    

4 各配送点的两点之间距离及配送量

两点连线	AB	AC	AD	AF	AE	AG	BC	CD	DF	EF	EG	FG
距离（ km）	9	12	12	24	20	21	9	10	19	6	1	6
配送量（ T）	0.8	0.7	1	1.1	1.75	1.15

5 计算配送中心A到各配送点、各配送点之间的最短距离

	A	B	C	D	E	F	G
A	0	9	12	12	20	24	21
B		0	9	19	29	33	30
C			0	10	32	29	33
D				0	25	19	25
E					0	6	1
F						0	6
G							0

6 计算各配送点组合的节约的里程数，并将之进行排序。

如DE之间的节约里程数＝(2AD+2AE)-(AD+DE+AE)=AD+AE-DE=12+20-25=7(两点之间都应以最短距离计算)

序号	1	2	3	4	5	6	7	8	9	10	11	11	11	11	11
组合	EG	FG	EF	DF	CD	BC	DG	CF	DE	BD	BE	BF	BG	CE	CG
里程数	40	39	38	17	14	12	8	7	7	2	0	0	0	0	0

7 按以上顺序考虑路线（即客户组合），同时考虑车辆的最大载重，形成车辆的线路安排；

7.1 第一条线路：AEGFA,配送货物量为：1.75+1.15+1.1＝4T，全程为：20+1+6+24=51km;

7.2 第二条线路：ADCBA,配送货物量为：1.7+0.8＝2.5T，全程为：9+9+10+12=40km;

AEGFDCBA=74km

91km-24(AF)-12(AD)+19(FD)=74km;